package chapter_05;


// 有序链表


/*
在有序链表中，数据是按照关键值有序排列的。有序链表的删除常常只限于删除在链表头部
的最小（或者最大）节点。不过，有时也用find()和delete()方法在整个链表中搜索某一
特定点。
一般，在大多数需要使用有序数组的场合也可以使用有序链表。有序链表优于有序数组的地方
是插入的速度（因为元素不需要移动），另外链表可以扩展到全部有效的使用内存，而数组只能局
限与一个固定的大小中。但是，有序链表实现起来比有序数组更困难一些。
有序链表也可以用于实现优先级队列，尽管堆是更常用的实现方法。
 */

public class SortedList {
    private Link2 first;

    public SortedList() {
        first = null;
    }

    public SortedList(int[] linkArr) {
        // 用来实现优先级队列的构造方法
        first = null;
        for (int j = 0; j < linkArr.length; j++)
            insert(linkArr[j]);
    }

    public boolean isEmpty() {
        return first == null;
    }

    public void insert(long key) {
        /*
        previous指向前一个节点，current指向当前的节点
         */
        Link2 newLink = new Link2(key);
        Link2 previous = null;
        Link2 current = first;

        while (current != null && key > current.dData) {
            previous = current;
            current = current.next;
        }

        if (previous == null)
            // 在表头或者链表为空的情况
            first = newLink;
        else
            previous.next = newLink;
        newLink.next = current;

        /*
        在链表上移动时，需要用一个previous引用，这样才能把前一个节点的next字段指向新的
        接点。创建新的节点后，把current变量设为first，准备搜索正确的插入点。这时也把previous
        设为null值，这步操作很重要，因为后面要用这个null值判断是否仍在表头。
        while循环和以前用来搜索插入点的代码类似，但是有一个附加的条件。如果当前检查的节点的
        关键字（current.dData）不再小于待插入的节点的关键之key，则循环结束；这是最常见的
        情况，即新关键值插在链表中部的某个地方。
        然而，如果current为null值，while循环也会停止。这种情况发生在表尾（最后一个元素的next
        域为null值），或者链表为空（first是null值）时。
        那么，当while循环结束时，current可能在表头，在链表中部，在表尾，或者链表是空的。
        如果current在表头，或者链表为空，previous将为null值；所以让first指向新的节点。否则
        current处在链表中部或结尾，就使previous的next字段指向新的节点。
        不论哪种情况，都让新节点的next字段指向current。如果在表尾，current为null值，则新
        节点的next字段也被应该设为这个值（null）。
         */
    }

    public Link2 remove() {
        Link2 temp = first;
        first = first.next;
        return temp;
    }

    public void displayList() {
        System.out.print("List (first-->last): ");
        Link2 current = first;
        while (current != null) {
            current.displayLink();
            current = current.next;
        }
        System.out.println();
    }
}


class SortedListApp {
    /*
    有序链表的效率
    在有序链表插入和删除某一项最多需要O(N)次比较（平均N/2），因为必须沿着链表上一步一
    步走才能找到正确的位置。然而，可以在O(1)的时间内找到或删除最小值，因为它总在表头。
    如果一个应用频繁地存储最小项，且不需要快速地插入，那么有序链表是一个有效的方案选择。
    例如，优先级队列可以用有序链表来实现。
     */

    static void sortedList() {
        // 有序链表
        SortedList theSortedList = new SortedList();
        theSortedList.insert(20);
        theSortedList.insert(40);
        theSortedList.displayList();

        theSortedList.insert(10);
        theSortedList.insert(30);
        theSortedList.insert(50);
        theSortedList.displayList();

        theSortedList.remove();
        theSortedList.displayList();
    }

    static void priorityQueue() {
        // 优先级队列
        int size = 10;
        int[] linkArray = new int[size];
        Link2[] resultArray = new Link2[size];

        System.out.print("Unsorted array: ");
        for (int j = 0; j < size; j++) {
            int n = (int) (java.lang.Math.random() * 99);
            linkArray[j] = n;
            System.out.print(linkArray[j] + " ");

        }
        System.out.println();

        SortedList theSortedList = new SortedList(linkArray);

        for (int j = 0; j < size; j++)
            resultArray[j] = theSortedList.remove();

        System.out.print("Sorted Array:   ");
        for (int j = 0; j < size; j++)
            System.out.print(resultArray[j].dData + " ");
        System.out.println();
    }

    public static void main(String[] args) {
//        sortedList();
        priorityQueue();
    }
}
